package 链表;

public class Demo01 {
    /*
    * 方法一: 快慢指针
    * 如果链表中存在环 快指针一定能够先走到末尾
    * 如果链表中不存在环 慢指针和快指针一定能够在环中相遇
    * */
    public static class Solution {
        public boolean hasCycle(ListNode head) {
            if(head == null || head.next == null){
                return false;
            }
            ListNode slow = head;
            ListNode quick = head.next;
            while(slow != quick){
                slow = slow.next;
                if(quick != null && quick.next != null){
                    quick = quick.next.next;
                }else{
                    return false;
                }
            }

            return true;
        }
    }
    /*
    * 方法二: 哈希表
    * 将遍历过的元素存储到哈希表中,如果再次遍历到了该节点则表示链表中存在环
    * 和上面的方法相比时间复杂度并没有差别,但是空间复杂度为O(n)
    * */
}
